#include <algorithm>
#include <cmath>
#include <iostream>
#include <iterator>
#include <limits>
#include <vector>

#include "predicates.h"

template <class RandIter>
RandIter quick_hull(RandIter& vertices_begin, RandIter& vertices_end, const point& leftmost, const point& rightmost)
{
    if (vertices_begin == vertices_end)
    {
        return vertices_begin;
    }

    RandIter uppermost_it = std::min_element(vertices_begin, vertices_end, [leftmost, rightmost](const point& a, const point& b)
                                                                           {
                                                                               return further_from_line_than_old_uppermost(leftmost, rightmost, a, b) == 1;
                                                                           });

    point uppermost = *uppermost_it;

    std::iter_swap(vertices_end - 1, uppermost_it);

    RandIter points_above_first_line = std::partition(vertices_begin, vertices_end, [leftmost, uppermost](const point& a)
                                                                                    {
                                                                                        return ((!(a == uppermost)) && (left_turn(leftmost, uppermost, a) == 1));
                                                                                    });

    RandIter resulting_bound = quick_hull(vertices_begin, points_above_first_line, leftmost, uppermost);

    if (resulting_bound == vertices_end)
    {
        return resulting_bound;
    }

    std::iter_swap(resulting_bound, vertices_end - 1);
    
    RandIter points_above_second_line = vertices_end;

    if (resulting_bound + 1 < points_above_first_line)
    {
        auto tmp = std::min(points_above_first_line, resulting_bound + 1 + (vertices_end - points_above_first_line));
        points_above_second_line = std::swap_ranges(resulting_bound + 1, tmp, vertices_end - (tmp - (resulting_bound + 1)));
    }
    
    points_above_second_line = std::partition(resulting_bound + 1, points_above_second_line, [uppermost, rightmost](const point& a)
                                                                                             {
                                                                                                 return ((!(a == uppermost)) && (left_turn(uppermost, rightmost, a) == 1));
                                                                                             });

    return quick_hull(resulting_bound + 1, points_above_second_line, uppermost, rightmost);
}

std::vector<point>::iterator quick_hull_wrapper(std::vector<point>& vertices)
{
    auto minmax = std::minmax_element(vertices.begin(), vertices.end());

    if (vertices.end() - 2 == minmax.second)
    {
        std::iter_swap(vertices.end() - 1, minmax.second);

        if (vertices.end() - 1 != minmax.first)
        {
            std::iter_swap(vertices.end() - 1, minmax.first);
        }
    } else
    {
        std::iter_swap(vertices.end() - 2, minmax.first);
        std::iter_swap(vertices.end() - 1, minmax.second);
    }

    point leftmost = *(vertices.end() - 2), rightmost = *(vertices.end() - 1);
    
    std::vector<point>::iterator lower_points = std::partition(vertices.begin(), vertices.end() - 2, [leftmost, rightmost](const point& a)
                                                                                                     {
                                                                                                         return ((left_turn(leftmost, rightmost, a)) == -1);
                                                                                                     });

    std::vector<point>::iterator convex_hull = quick_hull(vertices.begin(), lower_points, rightmost, leftmost);

    std::iter_swap(convex_hull, vertices.end() - 2);
    
    std::vector<point>::iterator upper_points = vertices.end() - 1;

    if (lower_points > convex_hull + 1)
    {
        auto tmp = std::min(lower_points, vertices.end() - lower_points + convex_hull);
        upper_points = std::swap_ranges(convex_hull + 1, tmp, vertices.end() - (tmp - (convex_hull + 1)));
    }
    
    upper_points = std::partition(convex_hull + 1, upper_points, [leftmost, rightmost](const point& a)
                                                                 {
                                                                     return ((left_turn(leftmost, rightmost, a)) == 1);
                                                                 });
    
    convex_hull = quick_hull(convex_hull + 1, upper_points, leftmost, rightmost);

    if (!(leftmost == rightmost))
    {
        std::iter_swap(convex_hull, vertices.end() - 1);
    }

    return convex_hull;
}